/*
 * @lc app=leetcode.cn id=322 lang=golang
 *
 * [322] 零钱兑换
 */

// 4. 动态规划
// @lc code=start
func coinChange(coins []int, amount int) int {
	if len(coins) == 0 {
		return -1
	}

	memo := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		minValue := math.MaxInt64
		for j := 0; j < len(coins); j++ { // 当前硬币额度比钱数小，然后看【钱数-当前硬币额度】需要几个硬币，找到最小数+1
			if coins[j] <= i && memo[i-coins[j]] < minValue {
				minValue = memo[i-coins[j]] + 1
			}
		}
		memo[i] = minValue
	}

	if memo[amount] == math.MaxInt64 {
		return -1
	} else {
		return memo[amount]
	}
}

// @lc code=end

// 3. 递归的同时，把结果记录下来，下次遇到该值就不用计算了
// @lc code=start
func coinChange(coins []int, amount int) int {
	if len(coins) == 0 {
		return -1
	}

	memo := make([]int, amount+1) // 100元，memo[100],memo有101个元素, 下标为金额，值就是该金额所需最小硬币数
	var recursion func(amount int) int
	recursion = func(amount int) int {
		if amount < 0 {
			return -1
		}

		if amount == 0 {
			return 0
		}

		if memo[amount] != 0 {
			return memo[amount]
		}

		minValue := math.MaxInt64
		for i := 0; i < len(coins); i++ {
			temp := recursion(amount - coins[i])
			if temp >= 0 && temp < minValue {
				minValue = temp + 1
			}
		}
		if minValue == math.MaxInt64 {
			memo[amount] = -1
		} else {
			memo[amount] = minValue
		}
		return memo[amount]
	}

	return recursion(amount)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

// 2. 直接递归 15/189 Time Limit Exceeded
// @lc code=start
func coinChange(coins []int, amount int) int {
	if len(coins) == 0 {
		return -1
	}

	ans := math.MaxInt64
	var recursion func(amount, count int)
	recursion = func(amount, count int) {
		if amount < 0 {
			return
		}

		if amount == 0 {
			ans = min(ans, count)
		}

		for i := 0; i < len(coins); i++ {
			recursion(amount-coins[i], count+1)
		}
	}

	recursion(amount, 0)
	if ans == math.MaxInt64 {
		return -1
	}
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// @lc code=end

// 1. 贪心 会失败，【1， 7， 10】 14，
// 会找到【10 1 1 1 1 1 1】
// @lc code=start
func coinChange(coins []int, amount int) int {
	sort.Ints(coins)

	var recursion func(coins []int, amount int) int
	recursion = func(coins []int, amount int) int {
		if len(coins) == 0 {
			return -1
		}

		if len(coins) == 1 && amount%coins[0] != 0 {
			return -1
		}

		for i := len(coins) - 1; i >= 0; i-- {
			coin := coins[i]

			if amount%coin == 0 {
				return amount / coin
			}

			dd := make([]int, len(coins))
			copy(dd, coins)

			cc := append(dd[:i], dd[i+1:]...)
			for j := amount / coin; j >= 0; j-- {
				count := recursion(cc, amount-coin*j)
				if count != -1 {
					return j + count
				}
			}
		}

		return -1
	}

	return recursion(coins, amount)
}

// @lc code=end

